package com.fr.lintcode;

import java.util.Stack;

public class Q367ii {

	/*
	 * @param expression: A string array
	 * 
	 * @return: The root of expression tree
	 */
	public ExpressionTreeNode build(String[] expression) {
		// write your code here
		if(expression == null){
			return null;
		}
		Stack<ExpressionTreeNode> nums = new Stack<>();
		Stack<ExpressionTreeNode> ops = new Stack<>();
		int length = expression.length;
		for(int i =0; i < length; i++){
			String s = expression[i];
			if("*".equals(s) || "/".equals(s)){
				if(ops.isEmpty()){
					ops.push(new ExpressionTreeNode(s));
				}else{
					ExpressionTreeNode before = ops.pop();
					if("(".equals(before.symbol)){
						ops.push(new ExpressionTreeNode(s));
					}
				}
			}else if("+".equals(s) || "-".equals(s)){
				
			}else if("(".equals(s)){
				
			}else if(")".equals(s)){
				
			}else{
				nums.push(new ExpressionTreeNode(s));
			}
		}
		return nums.pop();
	}

	public class ExpressionTreeNode {
		public String symbol;
		public ExpressionTreeNode left, right;

		public ExpressionTreeNode(String symbol) {
			this.symbol = symbol;
			this.left = this.right = null;
		}
	}

}
